//序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方
//式重构得到原数据。
//
// 请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串
//反序列化为原始的树结构。
//
// 提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的
//方法解决这个问题。
//
//
//
// 示例 1：
//
//
//输入：root = [1,2,3,null,null,4,5]
//输出：[1,2,3,null,null,4,5]
//
//
// 示例 2：
//
//
//输入：root = []
//输出：[]
//
//
// 示例 3：
//
//
//输入：root = [1]
//输出：[1]
//
//
// 示例 4：
//
//
//输入：root = [1,2]
//输出：[1,2]
//
//
//
//
// 提示：
//
//
// 树中结点数在范围 [0, 10⁴] 内
// -1000 <= Node.val <= 1000
//
//
// Related Topics 树 深度优先搜索 广度优先搜索 设计 字符串 二叉树 👍 1098 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

/*
 * Encodes a tree to a single string.
 */
function serialize(root: TreeNode | null): string {
    if (root === null) return JSON.stringify([]);

    let queue: TreeNode[] = [root];
    let serializeList: number[] = [];
    //? 层序遍历
    while (queue.length) {
        let len = queue.length;
        while (len > 0) {
            //? 将本次操作的结点出队
            const node = queue.shift();
            len--;
            if (node === null) {
                serializeList.push(null);
            } else {
                serializeList.push(node.val);
                node.left ? queue.push(node.left) : queue.push(null);
                node.right ? queue.push(node.right) : queue.push(null);
            }
        }
    }

    return JSON.stringify(serializeList);
};

function deserialize(data: string): TreeNode | null {
    let list: number[] = JSON.parse(data);

    if (list.length === 0) return null;

    let inx: number = 1;
    let root: TreeNode = new TreeNode(list[0]);
    let queue = [root];
    //? 同理是层序遍历
    while (queue.length) {
        const node = queue.shift();
        node.left = null;
        node.right = null;
        //? 不为空才创节点 并给左
        if (list[inx] !== null) {
            node.left = new TreeNode(list[inx]);
            queue.push(node.left);
        }
        inx++;
        //? 不为空才创节点 并给右
        if (list[inx] !== null) {
            node.right = new TreeNode(list[inx]);
            queue.push(node.right);
        }
        inx++;
    }

    return root;
};



/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */
//leetcode submit region end(Prohibit modification and deletion)
